home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 October / MACPOWER-1997-10.ISO.7z / MACPOWER-1997-10.ISO / AMUG / GAME / I Ching Connexion 2.32.sit / I Ching Connexion 2.3.2 ƒ / I Ching Connexion 2.3.2.rsrc / TEXT_7510_Programmer's Introduction.txt < prev    next >
Text File  |  1997-07-08  |  20KB  |  253 lines
  1.                    Programmer窶冱 Introduction
  2.  
  3.                             By Ed van Zon
  4.  
  5.  
  6.                                               How it started
  7.  
  8. Dear User,
  9.  
  10. Congratulations! You窶况e got a Macintosh computer to play with. At least, with me, that窶冱 what started the creation of the I Ching Connexion.
  11. I play with my computer much like I used to play with Mecano: constructing something new out of it窶冱 basic building parts. I窶冦 not really interested in the result (except that it has to work as intended), it窶冱 the screwing together that I like.
  12. So, when back in 1988 I acquired my first Macintosh (a second hand Mac Plus), the big question was: what to build with it? Preferably something that someone else could be interested in, and that hadn窶冲 already been done. I decided a program that could find and present transcendental solutions of the China Labyrinth (as it was then called), would be sufficiently challenging for me and might be of interest to my friend Christian Freeling , who already had a collection of interesting solutions to this puzzle. Christian, by the way, was the inspiring force to evolve that program to the one you窶决e looking at right now, in which the puzzle solving algorithm only plays a minor, albeit essential, part.
  13. _________________________________________________
  14.  
  15.                                   The Connexion: how it works
  16.  
  17. As explained in the Compiler's Introduction, The set, the China Labyrinth puzzle consists of 64 hexagons, that all have different combinations of 窶賄oors窶™ on the sides: there窶冱 1 hexagon with no doors, 6 have one door, etc.. In a transcendental solution every door is 窶歪onnected窶™ to a door of a neighbouring hexagon, and every side without a door has no neighbour. (When you drop the second rule you get a 窶歪ompact solution窶™.)
  18.  
  19. The program searches for a transcendental solution using a simple backtracking technique: it puts the hexagons on a hexagonal grid one by one while observing the rules. Besides that it assumes the part put together so far is part of a solution until proven otherwise, in which case the hexagon placed last is removed from the grid and another one put in its place. 
  20. Note that the rules can only be upheld in a completely finished solution; in a partial solution (i.e. an 窶˜unfinished窶™ part of a solution) we have to relax the first rule: in a partial solution a door doesn窶冲 have to be connected (yet) to a door of a neighbour. It is clear however that to yield a solution eventually a hexagon, with a corresponding door, must be put on the neighbouring position.
  21.  
  22. _________________________________________________
  23.  
  24.                                           The algorithm (in short):
  25.  
  26. A, start:
  27. The program starts by randomly picking a hexagon and placing it somewhere on the grid. Note that this one piece is  part of every  possible solution.
  28. B, find a spot that requires a piece:
  29. Since this is part of a solution, every  side with an 窶椀pen窶™ door will have to get a neighbouring hexagon. So, for the next step, just pick one of these sides. (*)
  30. C, find candidates for that spot:
  31. Determine which of the free pieces (the pieces that have not been put on the grid yet) could be put there as a neighbour, without breaking the (relaxed) rules.  If the part put together so far is part of a solution (assumption), any such solution must  have one  of these free pieces, the candidates, on exactly that spot. (**)
  32. D, try every candidate in turn:
  33. So put one of the candidates on the designated spot, and continue with B again. If this doesn窶冲 yield a solution, replace this candidate with the next one and continue with B. Repeat this until all candidates have been tried. If none of the candidates yields a solution, then the part put together so far cannot be part of  a solution, so we have to 窶話acktrack窶™ even further.
  34.  
  35. (*) special cases finding a spot:
  36. If there are no sides with an 窶椀pen窶™ door left, a so-called group is finished. 
  37. If, at the same time, all pieces have been put on the grid a solution is found! (To continue finding solutions, just go back to D and remove the last piece put.)
  38. If there are still some free pieces, the program proceeds by randomly picking one of the free pieces and placing it somewhere on the grid to start building a new group. (The groups are considered not to interfere with one another.) Note that if the part, consisting of the finished group(s), is part of a solution, putting this one piece also yields a part of any such solution. Continue with B.
  39.  
  40. (**) special case finding candidates:
  41. If there are no candidates, the part put together so far cannot be part of a solution, and you窶冤l have to go back to D and remove the last piece put.
  42.  
  43. _________________________________________________
  44.  
  45.                                                 Optimisations
  46.  
  47. All  solutions the algorithm described above will present are unique , not considering rotations. And it will, given enough time, find every possible  solution. You have to be patient though; it will take many millions of years to finish.
  48. It might even take an unpractical amount of time to find a first solution, depending on how the first, say, 40 pieces are put. The computer can spend years trying to place the last 24, without there being a solution possible, given the arrangement of the first 40.
  49. So I tried to speed things up a bit.
  50.  
  51. First, I made the program somewhat smarter in determining that a solution is not possible, given the part put together so far. E.g. if the part on the grid has more 窶椀pen窶™ doors pointing upwards than there are downward doors on the free pieces, there clearly isn窶冲  a solution possible. The program is a bit more refined still, but this is the idea.
  52.  
  53. Second, in step B, finding a spot that requires a piece, the algorithm picks one randomly out of the several possibilities at a certain moment. Since any  of the possibile spots will do for the algorithm, we might just as well take the spot that has the least number of candidates. This way, we keep this branch of the search tree at a minimum.
  54.  
  55. Third, a property of a transcendental solution is that the number of holes is the same as the number of groups. Note there are at least two groups (the hexagon with no doors, and the rest). So a solution must have at least two holes.  I therefore tweaked the program (as suggested by Christian, see Interpretation - the Connexion,  In the light of the multitude displayed...) in such a way that it would create holes early in the process. While this wouldn窶冲 speed things up if we were to find all  solutions, it will speed up finding a first.
  56. For this, note that a hole is surrounded by (at least) six pieces, that have doors at an angle of 120ﾋš (and no door in between). So, in step D, trying every candidate in turn, the candidate that has (the most of) these 120ﾋš angled doors is tried first. A consequence is that those kind of pieces are put on the grid early in the process, and relatively close to each other, so chances that a hole will be formed are made higher.
  57.  
  58. Fourth, also in step D, the candidates with a high number of doors are tried before the ones with few doors. Experience learns that, when most pieces are put on the grid, the chances of finding a solution is higher if the remaining free pieces have relatively few doors. So we want to get rid of the 窶鷲igher窶™ pieces early in the process.
  59.  
  60. Even with the optimisations mentioned above, it happened fairly often that the program had put a part on the grid that couldn窶冲 be part of a solution, but it was still frantically trying to complete it (and would continue trying for the next year or so). So, I decided (Christian approved, and not just on practical grounds as you can read in Interpretation - the Connexion) to just start all over again if a solution wasn窶冲 found within a certain amount of steps (the action of putting a candidate on it窶冱 spot counts as one step).
  61. This is rather drastic, for now the program isn窶冲 going to find all possible solutions anymore, but it assures that one will be found within a reasonable amount of time (depending on the hardware). Well, actually, there is no guarantee for this either, but statistics dictate one will be found reasonably quick most of the time.
  62. For the number of solutions the program will find in an hour, there is an optimum in the number of steps the program is allowed to take before starting all over. This optimum is experimentally determined at 384.
  63.  
  64. The second, third and fourth optimisation still allow for a lot of randomness. There might be several spots with the least number of candidates; there might be several candidates with the highest number of doors. In such cases the program randomly picks one.
  65. As you will note, the result is that the program never presents the same solution twice, and there is still an enormous variation in the solutions you窶冤l get.
  66.  
  67. If you really want to, it is possible to adjust these optimisations, although we do not advise it for practical purposes. If you press 竚˜-Y the 窶牢earch Options窶™ dialog will be presented to you. (Remember that a 窶賄emand窶™ is higher if that spot has less candidates, and a 窶湾iece窶™ is higher if it has more doors.)
  68. What you might want to do is set 窶湾lace Pieces窶™ at random. This can be done in the 窶榔references窶™ dialog too with the 窶牢earch Connexion窶™ popup.  On average it will take quite a bit longer to find a solution, but they are of a somewhat different form than the ones the program normally shows; e.g. solutions with two groups that have holes, which are very unlike to be found with the normal settings. Interesting as a screensaver, maybe.
  69. _________________________________________________
  70.  
  71.                                 The Octopuszle: how could it work
  72.  
  73. In the 窶呂ompiler's Introduction,  The Octopuszle窶™ the Octopuszle is introduced as one of the generalisations based on the original China Labyrinth, and as one of the important motivations for creating the I Ching Connexion. Specifically, the observation that two persons independently found solutions to the Octopuszle that have the same diagonal complex, was the major incentive.
  74.  
  75. Now, how difficult is it to construct a solution with the same diagonal pattern as some given solution? I suggest you try it yourself.
  76. Could a computer program achieve it, within reasonable time? Well, I haven窶冲 written such a program, but it might be constructed analogous to the Connexion solving algorithm:
  77.  
  78. First note we窶决e looking for a compact solution in a 16x16 square, with a fixed pattern of diagonals  coming from a known solution. So we know beforehand which spots require a piece (namely all 256); and 窶椀pen窶™ doors will always be orthogonal ones (the blue lines).
  79.  
  80. The algorithm (very short):
  81. A, find the spot with the least number of candidates.
  82. B, find the candidates for that spot.
  83. C, try every candidate in turn.
  84.  
  85. At the start, the corner positions have 4 candidates each, the positions on the border have 8 and the others all have 16 candidates. So, at the start, pick one of the corner spots.
  86. Note that, at any time, the number of candidates in step B will never exceed 4, because there will always be a spot that has at least two of its sides determined (in other words, there will always be a 窶歪orner窶™ spot).
  87. So an upper limit for the number of steps needed to complete the search for all  solutions is 4 to the 256th power.
  88. Compare this with the upper limit for the I Ching Connexion: 8 to the 64th power.
  89. Therefore, considering upper limits, it takes about 4^160 times longer to find all solutions for the Octopuszle (given a fixed diagonal complex) as the time needed for the I Ching Connexion. That is a factor of approximately   2.1 * 10^96.
  90.  
  91. How many solutions are there, given the diagonal pattern? Well, an upper limit is 16 * 16! 竕ˆ 3.35 * 10^14. We feel that the number of solutions to the I Ching Connexion highly exceeds this number.
  92.  
  93. Summing up, it takes a hell of a lot more time to find less solutions. 
  94. So how long would it take to find one  solution. Well, on average, more than a hell of a lot longer!
  95. Suppose, we would find a solution for the Connexion at every clock-cycle of the computer (this is a ridiculously short time). Let窶冱 say our computer runs at 1000 MHz (never heard of one, at the moment).
  96. It would then take more then 6.7 * 10^79 years to find one for the Octopuszle (with fixed diagonals), on average.
  97.  
  98. Even with the 窶˜start-all-over窶™ trick, we would be incredibly lucky to find a solution within 10 years.
  99. On the other hand, we have been  incredibly lucky finding the two solutons you can see in this program; i.e., to me it窶冱 a highly remarkable coincidence, to Christian it窶冱 the hand of Someone up there.
  100.  
  101. _________________________________________________
  102.  
  103.                                 The natal hexagram display
  104.  
  105. The display of the natal hexagram is a bit simple: just the 窶櫓arlier Heaven窶™ and 窶廊ater Heaven窶™ hexagrams are displayed, with their controlling line inverted. Each line of the hexagram stands for a 6 or 9 year period (as explained in Intro Astro, The Natal Hexagram) and it is up to the user to divide the subject窶冱 life into these periods; the program doesn窶冲 help you with that.
  106.  
  107. It is also possible to 窶呂onnect窶™ the natal hexagrams although it is not clear what significance that would have. But if you can relate any meaning to a natal Connexion, you窶决e welcome to do so. 
  108. You can always choose 窶路ide Connexion窶™ to return to the simple display.
  109.  
  110. _________________________________________________
  111.  
  112.                                                    Credits
  113.  
  114. This program wouldn窶冲 have seen daylight if it wasn窶冲 for the inspiration of Christian Freeling. 
  115. Textcompilation, texts (except the one you窶决e reading now and balloontext) and all of the artwork are from his hands too.
  116.  
  117. The I Ching text in this program is basically the translation James Legge made (published in 1882, England) of the Imperial Edition of the I (published in 1715, China).
  118.  
  119. The link between the I Ching and astrology was suggested to us by Gerard Dijkman. The astrological data and calculation method are from 窶狼he Astrology of I Ching窶™ by Dr. W.K. Chu and W.A. Sherrill.
  120.  
  121.  
  122. The I Ching Connexion is written using the Symantec C development environment, so portions ﾂｩ Symantec Corporation.
  123.  
  124. Special thanks goes to Marco Piovanelli for his (free) Worldscript Aware Styled Text Engine (WASTE), which proved a considerable improvement over Apple窶冱 TextEdit. 
  125. WASTE text engine ﾂｩ 1993-1995 Marco Piovanelli.
  126.  
  127. I used quite a bit of sample code, bits and pieces I found on the Internet. Sometimes I modified things to serve my needs.
  128. In no particular order, credits and my thanks go to:
  129.  
  130. F. Pottier for a set of (Pascal) routines to handle floating windows. Originally based on a set of C routines written by Patrick Doane.
  131.  
  132. Troy Gaul of     Infinity Systems for the Infinity Windoid WDEF ﾂｩ 1991-95 Infinity Systems.
  133.  
  134. Glenn R. Howes for the Flag Control CDEF.
  135.  
  136. Jim Stout for his Groupbox, Popup Menu and Date&Time CDEFs, and a set of routines to handle movable modal dialogs.
  137.  
  138. Harold Ekstrom for his SliderCDEF ﾂｩ1993-1994.
  139.  
  140. Pete Gontier for a piece of asynchronous sound playing code.
  141.  
  142. Tony Myles for his SpriteWorld animation framework, and a set of handy dialog utility routines.
  143.  
  144. This program contains material from a version of the sample program 窶呂hassis窶™, which was originally created and copyrighted by Charles A. Hoffman.
  145. Some of the 窶呂hassis窶™ code was used as a starting base to handle the text-windows of the I Ching Connexion. I have changed much and added a lot.
  146.  
  147. The Connexion document windows are of my own design, as is all the other code not credited for above.
  148.  
  149. _________________________________________________
  150.  
  151.                                                    Legal stuff
  152.  
  153. I Ching Connexion ﾂｩ 1995-1997 MindSports
  154.  
  155. Portions ﾂｩ by others (see Program, Credits)
  156.  
  157. This software is distributed as shareware: if you like it please honor the shareware system and register for US$20. In return you will receive a registration code which allows you to save and print I Ching Connexion documents.
  158.  
  159. Registrations are handled by Kagi Software, and made easy using the 窶彝egister窶 program. If you're unfamiliar with that, please read the accompanying 窶廩ow to Register窶 document. Both the program and the document should be in the I Ching Connexion package.
  160.  
  161. Please note that 50% of the contributions I receive will be donated to UNICEF, the United Nations Children窶冱 Emergency Fund. 
  162.  
  163. You are allowed, even encouraged, to freely distribute unregistered versions of this program to anyone you like, provided it is not modified in any way and there窶冱 no charge for it; but it may not be included in any commercial package without our written consent.
  164.  
  165. This software is provided as is. No responsibility is taken for any damage it might cause. This software is not guaranteed to be useful for any purpose. Use at your own risk. 
  166.  
  167. _________________________________________________
  168.  
  169.                                               Version history
  170.  
  171. version 2.3.2:
  172. - Payment made easy; Kagi enters the picture. 
  173.  
  174. version 2.3.1:
  175. - Solar Software becomes MindSports
  176. - New site on the web: http://www.mindsports.net/
  177. - New e-mail address for Christian: christian@mindsports.net
  178.                                         and me: ed@mindsports.net
  179. - Backgrounds of the windows are now patterns.
  180.  
  181. version 2.3:
  182. - All cross-references in the texts are hyperlinked.
  183. - Improved graphics, with a choice of seven colors for the hexagons.
  184. - Allows manual entry of the outcome, so you can throw the coins 
  185.    yourself.
  186. - Date and time for the natal hexagram can now be entered directly 
  187.    using the keyboard.
  188. - Clicking on the time-box displays the current outcome; 
  189.    option-clicking gives you the 窶狼hrow the coins窶™ dialogue.
  190. - Option-click on a changing line in the 窶路exagram Meaning窶™ window
  191.    brings you to the commentaries on that line.
  192. - Allows entering the question first, followed by 窶狼hrow & Connect...窶™.
  193. - Alternates colors when a hexagram is both actual and future 
  194.    (or waning and waxing).
  195. - Prints waning & waxing hexagrams correctly now.
  196.  
  197. version 2.2:
  198. - Added a simple outcome display, so the program can be used for 
  199.   traditional divinations (that is: without a Connexion).
  200. - Made the changing lines more visible, and clickable in the 窶路exagram
  201.   Meaning窶™ window.
  202. - Switched to using the WASTE text engine, which brought along:
  203.    ﾂｷ Drag and drop
  204.    ﾂｷ Undo
  205.    ﾂｷ Embedded pictures
  206.    ﾂｷ Large texts (so Ta Chuan in two parts now, instead of four)
  207. - Added Color menu.
  208. - Added support for page navigation and text editing keys on extended
  209.   keyboard.
  210. - Optimised for PowerPC and 680x0 Macs (FAT version).
  211.  
  212. version 2.1: 
  213. - Added astro calculations (clock, natal) for the southern hemisphere.
  214.   Before these were only applicable to the northern hemisphere.
  215. - Reworked 窶朗atal data窶™ & 窶呂lock settings窶™ dialog. Hopefully, they窶决e
  216.   less confusing now.
  217.  
  218. version 2.0: 
  219. First public release
  220.  
  221. version 1.0: 
  222. A bare China Labyrinth solving program.
  223.  
  224. _________________________________________________
  225.  
  226.                                            How to reach me
  227.  
  228. If you experience problems with this software, or encounter bugs using it, I would like to hear about it. I might be able to fix it.
  229. I窶冦 open for any additional comment you would like to share about this program.
  230.  
  231. You can reach me on this postal address:
  232.  
  233. MindSports
  234. Ed van Zon
  235. P.O. Box 266
  236. 6700 AG  Wageningen
  237. Netherlands.
  238.  
  239. or on the internet address below. 
  240.  
  241. Have fun.
  242.  
  243.       □                          □
  244.  
  245.     ed@mindsports.net
  246.  
  247.    MindSports Home Page    http://www.mindsports.net/
  248.  
  249.                                                                      Wageningen, July 1997.
  250.  
  251. _________________________________________________
  252.  
  253.